#pragma once
#include<vector>
#include<string.h>
#include<iostream>
using namespace std;

//解决浮点key，负数key的仿函数,统统转成无符号数
template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

template<>
struct Hash<string>
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto e : str)
		{
			hash += hash*31 + e;
		}
		return hash & (0x7FFFFFFF);
	}
};

template<class K>
struct CMP
{
	bool operator()(const K& k1,const K& k2)
	{
		return k1 == k2;
	}
};


template<>
struct CMP<string>
{
	bool operator()(const string& st1, const string& st2)
	{
		return strcmp(st1.c_str(), st2.c_str()) == 0;
	}
};


namespace LinkHash
{
	template<class T>
	struct HashNode
	{
		HashNode(const T& data)
			:_data(data)
		{}

		HashNode<T>* _next = nullptr;
		T _data;
	};

	template<class K, class T, class KeyOfT, class HF = Hash<K>>
	class HashTable;

	template<class K, class T, class Ref, class Ptr,class KeyOfT,class HashFunc >
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;

		__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t index = hf(kot(_node->_data)) % (_pht->_tables.size());
				++index;
				while (index < _pht->_tables.size())
				{
					if (_pht->_tables[index])
						break;
					else
						++index;
				}
				//表走完了，没有找到下一个
				if (index == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[index];
				}
			}
			return *this;
		}

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		Node* _node;
		HashTable<K, T, KeyOfT, HashFunc>* _pht;
	};

	template<class K,class T,class KeyOfT,class HF>
	class HashTable
	{
		KeyOfT KOT;
		HF hf;
		CMP<K> cmp;

	public:
		friend struct __HTIterator<K, T, T&, T*, KeyOfT, HF>;
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, T&, T*, KeyOfT, HF> iterator;

		iterator begin()
		{
			if (_tables.size() == 0)//如果为空表
			{
				return end();
			}
			size_t i = 0;
			for (i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
					return iterator(_tables[i], this);
			}
			return end();
		}

		iterator end()
		{
			iterator it(nullptr,this);
			return it;
		}


		Node* Find(const K& key)
		{
			//如果表为空，则直接返回
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			size_t index = hf(key) % _tables.size();
			if (_tables[index] == nullptr)
			{
				return nullptr;
			}
			else
			{
				Node* cur = _tables[index];
				while (cur)
				{
					if (cmp(KOT(cur->_data) , key))
					{
						return cur;
					}
					else
					{
						cur = cur->_next;
					}
				}
				return nullptr;
			}
		}

		bool Insert(const T& data)
		{
			Node* exist = Find(KOT(data));
			if (exist != nullptr)//如果已经存在，则插入失败
			{
				return false;
			}
			if(_n == 0 || _tables.size() == _n)//扩容
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size()*2;
				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i] == nullptr)
					{
						continue;
					}
					else//扩容，把结点链接到新表中
					{
						Node* cur = _tables[i];
						while (cur)
						{
							size_t index = hf(KOT(cur->_data)) % newSize;
							Node* next = cur->_next;
							if (newTables[index] == nullptr)
							{
								newTables[index] = cur;
								cur->_next = nullptr;//很关键，新表位置第一次放，结点的下一个位置要置空
							}
							else//头插
							{
								cur->_next = newTables[index];
								newTables[index] = cur;
							}
							cur = next;
						}
						_tables[i] = nullptr;//旧表置空
					}
				}
				//交换新表旧表
				_tables.swap(newTables);
			}
			size_t index = hf(KOT(data)) % _tables.size();
			Node* newNode = new Node(data);//新结点
			if (_tables[index] == nullptr)
			{
				_tables[index] = newNode;
			}
			else//头插
			{
				newNode->_next = _tables[index];
				_tables[index] = newNode;
			}
			++_n;//增加新节点后加加有效值
			return true;
		}

		bool Erase(const K& key)
		{
			//如果表为空，则直接返回
			if (_tables.size() == 0)
			{
				return false;
			}
			size_t index = hf(key) % _tables.size();
			if (_tables[index] == nullptr)
			{
				return false;
			}
			else
			{
				Node* cur = _tables[index];
				Node* prev = nullptr;
				while (cur)
				{
					if (cmp(KOT(cur->_data) , key))
					{
						if (prev != nullptr)
						{
							prev->_next = cur->_next;
						}
						else
						{
							_tables[index] = cur->_next;
						}
						//如果为表中位置的拉链唯一元素，则delete前，先把该位置置空
						if (cur == _tables[index] && cur->_next == nullptr)
							_tables[index] = nullptr;
						delete cur;
						--_n;//减少有效元素
						return true;
					}
					else
					{
						cur = cur->_next;
						prev = cur;
					}
				}
				return false;
			}
		}	

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}
